<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
<head>
<meta http-equiv="content-type" content="text/html; charset=ISO-8859-1" />
<title>HuffmanEncoder xref</title>
<link type="text/css" rel="stylesheet" href="../../../../../../stylesheet.css" />
</head>
<body>
<div id="overview"><a href="../../../../../../../apidocs/com/totsp/gwittir/client/util/compress/HuffmanEncoder.html">View Javadoc</a></div><pre>

<a name="1" href="#1">1</a>   <em class="jxr_comment">/*</em>
<a name="2" href="#2">2</a>   <em class="jxr_comment"> * To change this template, choose Tools | Templates</em>
<a name="3" href="#3">3</a>   <em class="jxr_comment"> * and open the template in the editor.</em>
<a name="4" href="#4">4</a>   <em class="jxr_comment"> */</em>
<a name="5" href="#5">5</a>   <strong class="jxr_keyword">package</strong> com.totsp.gwittir.client.util.compress;
<a name="6" href="#6">6</a>   
<a name="7" href="#7">7</a>   <strong class="jxr_keyword">import</strong> java.util.ArrayList;
<a name="8" href="#8">8</a>   <strong class="jxr_keyword">import</strong> java.util.HashMap;
<a name="9" href="#9">9</a>   <strong class="jxr_keyword">import</strong> java.util.Iterator;
<a name="10" href="#10">10</a>  <strong class="jxr_keyword">import</strong> java.util.TreeSet;
<a name="11" href="#11">11</a>  
<a name="12" href="#12">12</a>  
<a name="13" href="#13">13</a>  <em class="jxr_javadoccomment">/**</em>
<a name="14" href="#14">14</a>  <em class="jxr_javadoccomment"> *</em>
<a name="15" href="#15">15</a>  <em class="jxr_javadoccomment"> * @author kebernet</em>
<a name="16" href="#16">16</a>  <em class="jxr_javadoccomment"> */</em>
<a name="17" href="#17">17</a>  <strong class="jxr_keyword">public</strong> <strong class="jxr_keyword">class</strong> <a href="../../../../../../com/totsp/gwittir/client/util/compress/HuffmanEncoder.html">HuffmanEncoder</a> {
<a name="18" href="#18">18</a>      ArrayList&lt;Byte&gt; binaryEncodedData = <strong class="jxr_keyword">new</strong> ArrayList&lt;Byte&gt;();
<a name="19" href="#19">19</a>      HashMap&lt;String, Byte&gt; encodingBitMap = <strong class="jxr_keyword">new</strong> HashMap&lt;String, Byte&gt;();
<a name="20" href="#20">20</a>      HashMap&lt;Character, Integer&gt; frequencyData = <strong class="jxr_keyword">new</strong> HashMap&lt;Character, Integer&gt;();
<a name="21" href="#21">21</a>      HashMap&lt;Character, String&gt; huffEncodeTable;
<a name="22" href="#22">22</a>      String rawData;
<a name="23" href="#23">23</a>      String stringEncodedData;
<a name="24" href="#24">24</a>      StringBuffer code = <strong class="jxr_keyword">new</strong> StringBuffer();
<a name="25" href="#25">25</a>      TreeSet&lt;HuffTree&gt; theTree = <strong class="jxr_keyword">new</strong> TreeSet&lt;HuffTree&gt;();
<a name="26" href="#26">26</a>  
<a name="27" href="#27">27</a>      <em class="jxr_comment">//This method populates a lookup table that relates eight</em>
<a name="28" href="#28">28</a>      <em class="jxr_comment">// bits represented as a String to eight actual bits for</em>
<a name="29" href="#29">29</a>      <em class="jxr_comment">// all possible combinations of eight bits.</em>
<a name="30" href="#30">30</a>      <strong class="jxr_keyword">void</strong> buildEncodingBitMap() {
<a name="31" href="#31">31</a>          <strong class="jxr_keyword">for</strong> (<strong class="jxr_keyword">int</strong> cnt = 0; cnt &lt;= 255; cnt++) {
<a name="32" href="#32">32</a>              StringBuffer workingBuf = <strong class="jxr_keyword">new</strong> StringBuffer();
<a name="33" href="#33">33</a>  
<a name="34" href="#34">34</a>              <strong class="jxr_keyword">if</strong> ((cnt &amp; 128) &gt; 0) {
<a name="35" href="#35">35</a>                  workingBuf.append(<span class="jxr_string">"1"</span>);
<a name="36" href="#36">36</a>              } <strong class="jxr_keyword">else</strong> {
<a name="37" href="#37">37</a>                  workingBuf.append(<span class="jxr_string">"0"</span>);
<a name="38" href="#38">38</a>              }
<a name="39" href="#39">39</a>  
<a name="40" href="#40">40</a>              ;
<a name="41" href="#41">41</a>  
<a name="42" href="#42">42</a>              <strong class="jxr_keyword">if</strong> ((cnt &amp; 64) &gt; 0) {
<a name="43" href="#43">43</a>                  workingBuf.append(<span class="jxr_string">"1"</span>);
<a name="44" href="#44">44</a>              } <strong class="jxr_keyword">else</strong> {
<a name="45" href="#45">45</a>                  workingBuf.append(<span class="jxr_string">"0"</span>);
<a name="46" href="#46">46</a>              }
<a name="47" href="#47">47</a>  
<a name="48" href="#48">48</a>              ;
<a name="49" href="#49">49</a>  
<a name="50" href="#50">50</a>              <strong class="jxr_keyword">if</strong> ((cnt &amp; 32) &gt; 0) {
<a name="51" href="#51">51</a>                  workingBuf.append(<span class="jxr_string">"1"</span>);
<a name="52" href="#52">52</a>              } <strong class="jxr_keyword">else</strong> {
<a name="53" href="#53">53</a>                  workingBuf.append(<span class="jxr_string">"0"</span>);
<a name="54" href="#54">54</a>              }
<a name="55" href="#55">55</a>  
<a name="56" href="#56">56</a>              ;
<a name="57" href="#57">57</a>  
<a name="58" href="#58">58</a>              <strong class="jxr_keyword">if</strong> ((cnt &amp; 16) &gt; 0) {
<a name="59" href="#59">59</a>                  workingBuf.append(<span class="jxr_string">"1"</span>);
<a name="60" href="#60">60</a>              } <strong class="jxr_keyword">else</strong> {
<a name="61" href="#61">61</a>                  workingBuf.append(<span class="jxr_string">"0"</span>);
<a name="62" href="#62">62</a>              }
<a name="63" href="#63">63</a>  
<a name="64" href="#64">64</a>              ;
<a name="65" href="#65">65</a>  
<a name="66" href="#66">66</a>              <strong class="jxr_keyword">if</strong> ((cnt &amp; 8) &gt; 0) {
<a name="67" href="#67">67</a>                  workingBuf.append(<span class="jxr_string">"1"</span>);
<a name="68" href="#68">68</a>              } <strong class="jxr_keyword">else</strong> {
<a name="69" href="#69">69</a>                  workingBuf.append(<span class="jxr_string">"0"</span>);
<a name="70" href="#70">70</a>              }
<a name="71" href="#71">71</a>  
<a name="72" href="#72">72</a>              ;
<a name="73" href="#73">73</a>  
<a name="74" href="#74">74</a>              <strong class="jxr_keyword">if</strong> ((cnt &amp; 4) &gt; 0) {
<a name="75" href="#75">75</a>                  workingBuf.append(<span class="jxr_string">"1"</span>);
<a name="76" href="#76">76</a>              } <strong class="jxr_keyword">else</strong> {
<a name="77" href="#77">77</a>                  workingBuf.append(<span class="jxr_string">"0"</span>);
<a name="78" href="#78">78</a>              }
<a name="79" href="#79">79</a>  
<a name="80" href="#80">80</a>              ;
<a name="81" href="#81">81</a>  
<a name="82" href="#82">82</a>              <strong class="jxr_keyword">if</strong> ((cnt &amp; 2) &gt; 0) {
<a name="83" href="#83">83</a>                  workingBuf.append(<span class="jxr_string">"1"</span>);
<a name="84" href="#84">84</a>              } <strong class="jxr_keyword">else</strong> {
<a name="85" href="#85">85</a>                  workingBuf.append(<span class="jxr_string">"0"</span>);
<a name="86" href="#86">86</a>              }
<a name="87" href="#87">87</a>  
<a name="88" href="#88">88</a>              ;
<a name="89" href="#89">89</a>  
<a name="90" href="#90">90</a>              <strong class="jxr_keyword">if</strong> ((cnt &amp; 1) &gt; 0) {
<a name="91" href="#91">91</a>                  workingBuf.append(<span class="jxr_string">"1"</span>);
<a name="92" href="#92">92</a>              } <strong class="jxr_keyword">else</strong> {
<a name="93" href="#93">93</a>                  workingBuf.append(<span class="jxr_string">"0"</span>);
<a name="94" href="#94">94</a>              }
<a name="95" href="#95">95</a>  
<a name="96" href="#96">96</a>              ;
<a name="97" href="#97">97</a>              encodingBitMap.put(workingBuf.toString(), (byte) (cnt));
<a name="98" href="#98">98</a>          } <em class="jxr_comment">//end for loop</em>
<a name="99" href="#99">99</a>      } <em class="jxr_comment">//end buildEncodingBitMap</em>
<a name="100" href="#100">100</a>       <em class="jxr_comment">//-----------------------------------------------------//</em>
<a name="101" href="#101">101</a> 
<a name="102" href="#102">102</a>     <em class="jxr_comment">//This method uses the Huffman tree in a recursive manner</em>
<a name="103" href="#103">103</a>     <em class="jxr_comment">// to create a bitcode for each character in the message.</em>
<a name="104" href="#104">104</a>     <em class="jxr_comment">// The bitcodes are different lengths with the shorter</em>
<a name="105" href="#105">105</a>     <em class="jxr_comment">// bitcodes corresponding to the characters with a high</em>
<a name="106" href="#106">106</a>     <em class="jxr_comment">// usage frequency value and the longer bitcodes</em>
<a name="107" href="#107">107</a>     <em class="jxr_comment">// corresponding to the characters with the lower</em>
<a name="108" href="#108">108</a>     <em class="jxr_comment">// frequency values.</em>
<a name="109" href="#109">109</a>     <em class="jxr_comment">//Note that this method receives a reference to the</em>
<a name="110" href="#110">110</a>     <em class="jxr_comment">// Huffman tree that was earlier contained as the only</em>
<a name="111" href="#111">111</a>     <em class="jxr_comment">// object in the TreeSet object.  (Because this method is</em>
<a name="112" href="#112">112</a>     <em class="jxr_comment">// recursive, it cannot conveniently work with the</em>
<a name="113" href="#113">113</a>     <em class="jxr_comment">// TreeSet object.</em>
<a name="114" href="#114">114</a> 
<a name="115" href="#115">115</a>     <em class="jxr_comment">//This method creates a Huffman encoding table as a</em>
<a name="116" href="#116">116</a>     <em class="jxr_comment">// HashMap object that relates the variable length</em>
<a name="117" href="#117">117</a>     <em class="jxr_comment">// bitcodes to the characters in the original message.</em>
<a name="118" href="#118">118</a>     <em class="jxr_comment">// The bitcodes are constructed as objects of type</em>
<a name="119" href="#119">119</a>     <em class="jxr_comment">// StringBuffer consisting of sequences of the characters</em>
<a name="120" href="#120">120</a>     <em class="jxr_comment">// 1 and 0.</em>
<a name="121" href="#121">121</a>     <em class="jxr_comment">//Each bitcode describes the traversal path from the root</em>
<a name="122" href="#122">122</a>     <em class="jxr_comment">// of the Huffman tree to a leaf on that tree.  Each time</em>
<a name="123" href="#123">123</a>     <em class="jxr_comment">// the path turns to the left, a 0 character is appended</em>
<a name="124" href="#124">124</a>     <em class="jxr_comment">// onto the StringBuffer object and becomes part of the</em>
<a name="125" href="#125">125</a>     <em class="jxr_comment">// resulting bitcode.  Each time the path turns to the</em>
<a name="126" href="#126">126</a>     <em class="jxr_comment">// right, a 1 character is appended onto the</em>
<a name="127" href="#127">127</a>     <em class="jxr_comment">// StringBuffer object.  When a leaf is reached, the</em>
<a name="128" href="#128">128</a>     <em class="jxr_comment">// character stored in that leaf is retrieved and put</em>
<a name="129" href="#129">129</a>     <em class="jxr_comment">// into the HashMap object as a key.  A String</em>
<a name="130" href="#130">130</a>     <em class="jxr_comment">// representation of the StringBuffer object is used as</em>
<a name="131" href="#131">131</a>     <em class="jxr_comment">// the value for that key in the HashMap.</em>
<a name="132" href="#132">132</a>     <em class="jxr_comment">//At completion,the HashMap object contains a series of</em>
<a name="133" href="#133">133</a>     <em class="jxr_comment">// keys consisting of the original characters in the</em>
<a name="134" href="#134">134</a>     <em class="jxr_comment">// message and a series of values as String objects</em>
<a name="135" href="#135">135</a>     <em class="jxr_comment">// (consisting only of 1 and 0 characters) representing</em>
<a name="136" href="#136">136</a>     <em class="jxr_comment">// the bitcodes that will eventually be used to encode</em>
<a name="137" href="#137">137</a>     <em class="jxr_comment">// the original message.</em>
<a name="138" href="#138">138</a>     <em class="jxr_comment">//Note that theHashMap object that is populated by this</em>
<a name="139" href="#139">139</a>     <em class="jxr_comment">// method is the data structure that is required later</em>
<a name="140" href="#140">140</a>     <em class="jxr_comment">// to decode the encoded message.</em>
<a name="141" href="#141">141</a>     <strong class="jxr_keyword">void</strong> createBitCodes(<a href="../../../../../../com/totsp/gwittir/client/util/compress/HuffTree.html">HuffTree</a> tree) {
<a name="142" href="#142">142</a>         <strong class="jxr_keyword">if</strong> (tree instanceof HuffNode) {
<a name="143" href="#143">143</a>             <em class="jxr_comment">// This is a node, not a leaf.  Process it as a node.</em>
<a name="144" href="#144">144</a> 
<a name="145" href="#145">145</a>             <em class="jxr_comment">//Cast to type HuffNode.</em>
<a name="146" href="#146">146</a>             <a href="../../../../../../com/totsp/gwittir/client/util/compress/HuffNode.html">HuffNode</a> node = (HuffNode) tree;
<a name="147" href="#147">147</a> 
<a name="148" href="#148">148</a>             <em class="jxr_comment">// Get and save the left and right branches</em>
<a name="149" href="#149">149</a>             <a href="../../../../../../com/totsp/gwittir/client/util/compress/HuffTree.html">HuffTree</a> left = node.getLeft();
<a name="150" href="#150">150</a>             <a href="../../../../../../com/totsp/gwittir/client/util/compress/HuffTree.html">HuffTree</a> right = node.getRight();
<a name="151" href="#151">151</a> 
<a name="152" href="#152">152</a>             <em class="jxr_comment">//Append a 0 onto the StringBuffer object.  Then make</em>
<a name="153" href="#153">153</a>             <em class="jxr_comment">// a recursive call to this method passing a</em>
<a name="154" href="#154">154</a>             <em class="jxr_comment">// reference to the left child as a parameter.  This</em>
<a name="155" href="#155">155</a>             <em class="jxr_comment">// recursive call will work its way all the way down</em>
<a name="156" href="#156">156</a>             <em class="jxr_comment">// to a leaf before returning.  Then it will be time</em>
<a name="157" href="#157">157</a>             <em class="jxr_comment">// to process the right path.</em>
<a name="158" href="#158">158</a>             code.append(<span class="jxr_string">"0"</span>);
<a name="159" href="#159">159</a>             createBitCodes(left);
<a name="160" href="#160">160</a> 
<a name="161" href="#161">161</a>             <em class="jxr_comment">//Return to here from recursive call on left child.</em>
<a name="162" href="#162">162</a> 
<a name="163" href="#163">163</a>             <em class="jxr_comment">//Delete the 0 from the end of the StringBuffer</em>
<a name="164" href="#164">164</a>             <em class="jxr_comment">// object to restore the contents of that object to</em>
<a name="165" href="#165">165</a>             <em class="jxr_comment">// the same state that it had before appending the 0</em>
<a name="166" href="#166">166</a>             <em class="jxr_comment">// and making the recursive call on the left branch.</em>
<a name="167" href="#167">167</a>             <em class="jxr_comment">//Now we will make a right turn.  Append a 1 to the</em>
<a name="168" href="#168">168</a>             <em class="jxr_comment">// StringBuffer object and make a recursive call to</em>
<a name="169" href="#169">169</a>             <em class="jxr_comment">// this method passing a reference to the right child</em>
<a name="170" href="#170">170</a>             <em class="jxr_comment">// as a parameter.  Once again, this recursive call</em>
<a name="171" href="#171">171</a>             <em class="jxr_comment">// will work its way all the  way down to a leaf</em>
<a name="172" href="#172">172</a>             <em class="jxr_comment">// before returning.</em>
<a name="173" href="#173">173</a>             code.deleteCharAt(code.length() - 1); <em class="jxr_comment">//Delete the 0.</em>
<a name="174" href="#174">174</a>             code.append(<span class="jxr_string">"1"</span>);
<a name="175" href="#175">175</a>             createBitCodes(right);
<a name="176" href="#176">176</a> 
<a name="177" href="#177">177</a>             <em class="jxr_comment">//Return to here from recursive call on right child.</em>
<a name="178" href="#178">178</a> 
<a name="179" href="#179">179</a>             <em class="jxr_comment">//Delete the character most recently appended to the</em>
<a name="180" href="#180">180</a>             <em class="jxr_comment">// StringBuffer object and return from this recursive</em>
<a name="181" href="#181">181</a>             <em class="jxr_comment">// call to the method.  The character is deleted</em>
<a name="182" href="#182">182</a>             <em class="jxr_comment">// because control is being transferred back one</em>
<a name="183" href="#183">183</a>             <em class="jxr_comment">// level in the recursive process and the</em>
<a name="184" href="#184">184</a>             <em class="jxr_comment">// StringBuffer object must be restored to the same</em>
<a name="185" href="#185">185</a>             <em class="jxr_comment">// state that it had when this recursive call was</em>
<a name="186" href="#186">186</a>             <em class="jxr_comment">// made.</em>
<a name="187" href="#187">187</a>             code.deleteCharAt(code.length() - 1);
<a name="188" href="#188">188</a>         } <strong class="jxr_keyword">else</strong> {
<a name="189" href="#189">189</a>             <em class="jxr_comment">//This is a leaf.  Process it as such.</em>
<a name="190" href="#190">190</a>             <em class="jxr_comment">//Cast the object to type HuffLeaf.</em>
<a name="191" href="#191">191</a>             <a href="../../../../../../com/totsp/gwittir/client/util/compress/HuffLeaf.html">HuffLeaf</a> leaf = (HuffLeaf) tree;
<a name="192" href="#192">192</a> 
<a name="193" href="#193">193</a>             <em class="jxr_comment">//Put an entry into the HashMap.  The HashMap</em>
<a name="194" href="#194">194</a>             <em class="jxr_comment">// key consists of the character value stored in the</em>
<a name="195" href="#195">195</a>             <em class="jxr_comment">// leaf. The value in the HashMap consists of the</em>
<a name="196" href="#196">196</a>             <em class="jxr_comment">// contents of the StringBuffer object representing</em>
<a name="197" href="#197">197</a>             <em class="jxr_comment">// the path from the root of the tree to the leaf.</em>
<a name="198" href="#198">198</a>             <em class="jxr_comment">// This is the bitcode and is stored in the HashMap</em>
<a name="199" href="#199">199</a>             <em class="jxr_comment">// as a String consisting of only 1 and 0 characters.</em>
<a name="200" href="#200">200</a>             huffEncodeTable.put((<strong class="jxr_keyword">char</strong>) (leaf.getValue()), code.toString());
<a name="201" href="#201">201</a>         } <em class="jxr_comment">//end else</em>
<a name="202" href="#202">202</a>     } <em class="jxr_comment">//end createBitCodes</em>
<a name="203" href="#203">203</a>       <em class="jxr_comment">//-----------------------------------------------------//</em>
<a name="204" href="#204">204</a> 
<a name="205" href="#205">205</a>     <em class="jxr_comment">//This method creates a frequency chart that identifies</em>
<a name="206" href="#206">206</a>     <em class="jxr_comment">// each of the individual characters in the original</em>
<a name="207" href="#207">207</a>     <em class="jxr_comment">// message and the number of times that each character</em>
<a name="208" href="#208">208</a>     <em class="jxr_comment">// appeared in the message.  The results are stored in</em>
<a name="209" href="#209">209</a>     <em class="jxr_comment">// a HashMap with the characters being the keys and the</em>
<a name="210" href="#210">210</a>     <em class="jxr_comment">// usage frequency of each character being the</em>
<a name="211" href="#211">211</a>     <em class="jxr_comment">// corresponding HashMap value for that key.</em>
<a name="212" href="#212">212</a>     <strong class="jxr_keyword">void</strong> createFreqData() {
<a name="213" href="#213">213</a>         <strong class="jxr_keyword">for</strong> (<strong class="jxr_keyword">int</strong> cnt = 0; cnt &lt; rawData.length(); cnt++) {
<a name="214" href="#214">214</a>             <strong class="jxr_keyword">char</strong> key = rawData.charAt(cnt);
<a name="215" href="#215">215</a> 
<a name="216" href="#216">216</a>             <strong class="jxr_keyword">if</strong> (frequencyData.containsKey(key)) {
<a name="217" href="#217">217</a>                 <strong class="jxr_keyword">int</strong> value = frequencyData.get(key);
<a name="218" href="#218">218</a>                 value += 1;
<a name="219" href="#219">219</a>                 frequencyData.put(key, value);
<a name="220" href="#220">220</a>             } <strong class="jxr_keyword">else</strong> {
<a name="221" href="#221">221</a>                 frequencyData.put(key, 1);
<a name="222" href="#222">222</a>             } <em class="jxr_comment">//end else</em>
<a name="223" href="#223">223</a>         } <em class="jxr_comment">//end for loop</em>
<a name="224" href="#224">224</a>     } <em class="jxr_comment">//end createFreqData</em>
<a name="225" href="#225">225</a>       <em class="jxr_comment">//-----------------------------------------------------//</em>
<a name="226" href="#226">226</a> 
<a name="227" href="#227">227</a>     <em class="jxr_comment">//This inner class is used to construct a leaf object in</em>
<a name="228" href="#228">228</a>     <em class="jxr_comment">// the Huffman tree.</em>
<a name="229" href="#229">229</a>     <em class="jxr_comment">//End HuffLeaf class</em>
<a name="230" href="#230">230</a>     <em class="jxr_comment">//=====================================================//</em>
<a name="231" href="#231">231</a> 
<a name="232" href="#232">232</a>     <em class="jxr_comment">//Assemble the HuffLeaf objects into a HuffTree object.</em>
<a name="233" href="#233">233</a>     <em class="jxr_comment">// A HuffTree object is a special form of a binary tree</em>
<a name="234" href="#234">234</a>     <em class="jxr_comment">// consisting of properly linked HuffNode objects and</em>
<a name="235" href="#235">235</a>     <em class="jxr_comment">// HuffLeaf objects.</em>
<a name="236" href="#236">236</a>     <em class="jxr_comment">//When the method terminates, the HuffTree object</em>
<a name="237" href="#237">237</a>     <em class="jxr_comment">// remains as the only object stored in the TreeSet</em>
<a name="238" href="#238">238</a>     <em class="jxr_comment">// object that previously contained all of the HuffLeaf</em>
<a name="239" href="#239">239</a>     <em class="jxr_comment">// objects.  This is because all of the HuffLeaf</em>
<a name="240" href="#240">240</a>     <em class="jxr_comment">// objects have been removed from the TreeSet object</em>
<a name="241" href="#241">241</a>     <em class="jxr_comment">// and combined with HuffNode objects to form the</em>
<a name="242" href="#242">242</a>     <em class="jxr_comment">// Huffman tree (as represented by the single HuffTree</em>
<a name="243" href="#243">243</a>     <em class="jxr_comment">// object).</em>
<a name="244" href="#244">244</a>     <em class="jxr_comment">//The method contains two sections of code that can be</em>
<a name="245" href="#245">245</a>     <em class="jxr_comment">// enabled to display:</em>
<a name="246" href="#246">246</a>     <em class="jxr_comment">// 1. The contents of the original TreeSet object.</em>
<a name="247" href="#247">247</a>     <em class="jxr_comment">// 2. The contents of the TreeSet object for each</em>
<a name="248" href="#248">248</a>     <em class="jxr_comment">//    iteration during which HuffLeaf objects are being</em>
<a name="249" href="#249">249</a>     <em class="jxr_comment">//    combined with HuffNode objects to form the final</em>
<a name="250" href="#250">250</a>     <em class="jxr_comment">//    HuffTree object.</em>
<a name="251" href="#251">251</a>     <em class="jxr_comment">// This display is very useful for understanding how the</em>
<a name="252" href="#252">252</a>     <em class="jxr_comment">// Huffman tree is constructed.  However, this code</em>
<a name="253" href="#253">253</a>     <em class="jxr_comment">// should be enabled only for small trees because it</em>
<a name="254" href="#254">254</a>     <em class="jxr_comment">// generates a very large amount of output.</em>
<a name="255" href="#255">255</a> 
<a name="256" href="#256">256</a>     <em class="jxr_comment">//The HuffTree object is constructed by:</em>
<a name="257" href="#257">257</a>     <em class="jxr_comment">// 1. Extracting pairs of HuffLeaf or HuffNode objects</em>
<a name="258" href="#258">258</a>     <em class="jxr_comment">//    from the TreeSet object in ascending order based</em>
<a name="259" href="#259">259</a>     <em class="jxr_comment">//    on their frequency value.</em>
<a name="260" href="#260">260</a>     <em class="jxr_comment">// 2. Using the pair of extracted objects to construct</em>
<a name="261" href="#261">261</a>     <em class="jxr_comment">//    a new HuffNode object where the two extracted</em>
<a name="262" href="#262">262</a>     <em class="jxr_comment">//    objects become children of the new HuffNode</em>
<a name="263" href="#263">263</a>     <em class="jxr_comment">//    object, and where the frequency value stored in</em>
<a name="264" href="#264">264</a>     <em class="jxr_comment">//    the new HuffNode object is the sum of the</em>
<a name="265" href="#265">265</a>     <em class="jxr_comment">//    frequency values in the two child objects.</em>
<a name="266" href="#266">266</a>     <em class="jxr_comment">// 3. Removing the two original HuffLeaf or HuffNode</em>
<a name="267" href="#267">267</a>     <em class="jxr_comment">//    objects from the TreeSet and adding the new</em>
<a name="268" href="#268">268</a>     <em class="jxr_comment">//    HuffNode object to the TreeSet object.  The</em>
<a name="269" href="#269">269</a>     <em class="jxr_comment">//    position of the new HuffNode object in the Treeset</em>
<a name="270" href="#270">270</a>     <em class="jxr_comment">//    object is determined by its frequency value</em>
<a name="271" href="#271">271</a>     <em class="jxr_comment">//    relative to the other HuffNode or HuffLeaf objects</em>
<a name="272" href="#272">272</a>     <em class="jxr_comment">//    in the collection. The new HuffNode object will</em>
<a name="273" href="#273">273</a>     <em class="jxr_comment">//    eventually become a child of another new HuffNode</em>
<a name="274" href="#274">274</a>     <em class="jxr_comment">//    object unless it ends up as the root of the</em>
<a name="275" href="#275">275</a>     <em class="jxr_comment">//    HuffTree object.</em>
<a name="276" href="#276">276</a>     <em class="jxr_comment">// 4. Continuing this process until the TreeSet object</em>
<a name="277" href="#277">277</a>     <em class="jxr_comment">//    contains a single object of type HuffTree.</em>
<a name="278" href="#278">278</a>     <strong class="jxr_keyword">void</strong> createHuffTree() {
<a name="279" href="#279">279</a>         <em class="jxr_comment">//Enable the following statements to see the original</em>
<a name="280" href="#280">280</a>         <em class="jxr_comment">// contents of the TreeSet object. Do this only for</em>
<a name="281" href="#281">281</a>         <em class="jxr_comment">// small trees because it generates lots of output.</em>
<a name="282" href="#282">282</a>         <em class="jxr_comment">/*</em>
<a name="283" href="#283">283</a> <em class="jxr_comment">            System.out.println("nnDisplay Original TreeSet");</em>
<a name="284" href="#284">284</a> <em class="jxr_comment">            Iterator &lt;HuffTree&gt; originalIter = theTree.iterator();</em>
<a name="285" href="#285">285</a> <em class="jxr_comment">            while(originalIter.hasNext()){</em>
<a name="286" href="#286">286</a> <em class="jxr_comment">              System.out.println(</em>
<a name="287" href="#287">287</a> <em class="jxr_comment">                              "nHuffNode, HuffLeaf, or HuffTree");</em>
<a name="288" href="#288">288</a> <em class="jxr_comment">              displayHuffTree(originalIter.next(),0);</em>
<a name="289" href="#289">289</a> <em class="jxr_comment">            }//end while loop</em>
<a name="290" href="#290">290</a> <em class="jxr_comment">            //End code to display the TreeSet</em>
<a name="291" href="#291">291</a> <em class="jxr_comment">        */</em>
<a name="292" href="#292">292</a> 
<a name="293" href="#293">293</a>         <em class="jxr_comment">//Iterate on the size of the TreeSet object until all</em>
<a name="294" href="#294">294</a>         <em class="jxr_comment">// of the elements have been combined into a single</em>
<a name="295" href="#295">295</a>         <em class="jxr_comment">// element of type HuffTree</em>
<a name="296" href="#296">296</a>         <strong class="jxr_keyword">while</strong> (theTree.size() &gt; 1) {
<a name="297" href="#297">297</a>             <em class="jxr_comment">//Get, save, and remove the first two elements.</em>
<a name="298" href="#298">298</a>             <a href="../../../../../../com/totsp/gwittir/client/util/compress/HuffTree.html">HuffTree</a> left = theTree.first();
<a name="299" href="#299">299</a>             theTree.remove(left);
<a name="300" href="#300">300</a> 
<a name="301" href="#301">301</a>             <a href="../../../../../../com/totsp/gwittir/client/util/compress/HuffTree.html">HuffTree</a> right = theTree.first();
<a name="302" href="#302">302</a>             theTree.remove(right);
<a name="303" href="#303">303</a> 
<a name="304" href="#304">304</a>             <em class="jxr_comment">//Combine the two saved elements into a new element</em>
<a name="305" href="#305">305</a>             <em class="jxr_comment">// of type HuffNode and add it to the TreeSet</em>
<a name="306" href="#306">306</a>             <em class="jxr_comment">// object.</em>
<a name="307" href="#307">307</a>             <a href="../../../../../../com/totsp/gwittir/client/util/compress/HuffNode.html">HuffNode</a> tempNode = <strong class="jxr_keyword">new</strong> <a href="../../../../../../com/totsp/gwittir/client/util/compress/HuffNode.html">HuffNode</a>(left.getFrequency() +
<a name="308" href="#308">308</a>                     right.getFrequency(), left, right);
<a name="309" href="#309">309</a>             theTree.add(tempNode);
<a name="310" href="#310">310</a> 
<a name="311" href="#311">311</a>             <em class="jxr_comment">//Enable the following statements to see the HuffTree</em>
<a name="312" href="#312">312</a>             <em class="jxr_comment">// being created from HuffNode and HuffLeaf objects.</em>
<a name="313" href="#313">313</a>             <em class="jxr_comment">// Do this only for small trees because it will</em>
<a name="314" href="#314">314</a>             <em class="jxr_comment">// generate a lot of output.</em>
<a name="315" href="#315">315</a>             <em class="jxr_comment">/*</em>
<a name="316" href="#316">316</a> <em class="jxr_comment">                  System.out.println("nnDisplay Working TreeSet");</em>
<a name="317" href="#317">317</a> <em class="jxr_comment">                  Iterator &lt;HuffTree&gt; workingIter = theTree.iterator();</em>
<a name="318" href="#318">318</a> <em class="jxr_comment">                  while(workingIter.hasNext()){</em>
<a name="319" href="#319">319</a> <em class="jxr_comment">                    System.out.println(</em>
<a name="320" href="#320">320</a> <em class="jxr_comment">                                  "nHuffNode, HuffLeaf, or HuffTree");</em>
<a name="321" href="#321">321</a> <em class="jxr_comment">                    displayHuffTree(workingIter.next(),0);</em>
<a name="322" href="#322">322</a> <em class="jxr_comment">                  }//end while loop</em>
<a name="323" href="#323">323</a> <em class="jxr_comment">                  //End code to display the TreeSet</em>
<a name="324" href="#324">324</a> <em class="jxr_comment">            */</em>
<a name="325" href="#325">325</a>         } <em class="jxr_comment">//end while</em>
<a name="326" href="#326">326</a>     } <em class="jxr_comment">//end createHuffTree</em>
<a name="327" href="#327">327</a>       <em class="jxr_comment">//-----------------------------------------------------//</em>
<a name="328" href="#328">328</a> 
<a name="329" href="#329">329</a>     <em class="jxr_comment">//This method creates a HuffLeaf object for each char</em>
<a name="330" href="#330">330</a>     <em class="jxr_comment">// identified in the frequency chart.  The HuffLeaf</em>
<a name="331" href="#331">331</a>     <em class="jxr_comment">// objects are stored in a TreeSet object.  Each HuffLeaf</em>
<a name="332" href="#332">332</a>     <em class="jxr_comment">// object encapsulates the character as well as the</em>
<a name="333" href="#333">333</a>     <em class="jxr_comment">// number of times that the character appeared in the</em>
<a name="334" href="#334">334</a>     <em class="jxr_comment">// original message.</em>
<a name="335" href="#335">335</a>     <strong class="jxr_keyword">void</strong> createLeaves() {
<a name="336" href="#336">336</a>         Iterator&lt;Character&gt; enumerator = frequencyData.keySet().iterator();
<a name="337" href="#337">337</a> 
<a name="338" href="#338">338</a>         <strong class="jxr_keyword">while</strong> (enumerator.hasNext()) {
<a name="339" href="#339">339</a>             Character nextKey = enumerator.next();
<a name="340" href="#340">340</a>             theTree.add(<strong class="jxr_keyword">new</strong> <a href="../../../../../../com/totsp/gwittir/client/util/compress/HuffLeaf.html">HuffLeaf</a>(nextKey, frequencyData.get(nextKey)));
<a name="341" href="#341">341</a>         } <em class="jxr_comment">//end while</em>
<a name="342" href="#342">342</a>     } <em class="jxr_comment">//end createLeaves</em>
<a name="343" href="#343">343</a>       <em class="jxr_comment">//-----------------------------------------------------//</em>
<a name="344" href="#344">344</a> 
<a name="345" href="#345">345</a>     <em class="jxr_comment">//This method displays a table showing the relationship</em>
<a name="346" href="#346">346</a>     <em class="jxr_comment">// between the characters in the original message and the</em>
<a name="347" href="#347">347</a>     <em class="jxr_comment">// bitcodes that will ultimately replace each of those</em>
<a name="348" href="#348">348</a>     <em class="jxr_comment">// characters to produce the Huffman-encoded message.</em>
<a name="349" href="#349">349</a>     <strong class="jxr_keyword">void</strong> displayBitCodes() {
<a name="350" href="#350">350</a>         Iterator&lt;Character&gt; enumerator = huffEncodeTable.keySet().iterator();
<a name="351" href="#351">351</a> 
<a name="352" href="#352">352</a>         <strong class="jxr_keyword">while</strong> (enumerator.hasNext()) {
<a name="353" href="#353">353</a>             Character nextKey = enumerator.next();
<a name="354" href="#354">354</a>             System.out.println(nextKey + <span class="jxr_string">" "</span> + huffEncodeTable.get(nextKey));
<a name="355" href="#355">355</a>         }
<a name="356" href="#356">356</a>     }
<a name="357" href="#357">357</a> 
<a name="358" href="#358">358</a>     <em class="jxr_comment">//This method displays the contents of the frequency</em>
<a name="359" href="#359">359</a>     <em class="jxr_comment">// chart created by the method named createFreqData.</em>
<a name="360" href="#360">360</a>     <strong class="jxr_keyword">void</strong> displayFreqData() {
<a name="361" href="#361">361</a>         System.out.println(<span class="jxr_string">"nFrequency Data"</span>);
<a name="362" href="#362">362</a> 
<a name="363" href="#363">363</a>         Iterator&lt;Character&gt; enumerator = frequencyData.keySet().iterator();
<a name="364" href="#364">364</a> 
<a name="365" href="#365">365</a>         <strong class="jxr_keyword">while</strong> (enumerator.hasNext()) {
<a name="366" href="#366">366</a>             Character nextKey = enumerator.next();
<a name="367" href="#367">367</a>             System.out.println(nextKey + <span class="jxr_string">" "</span> + frequencyData.get(nextKey));
<a name="368" href="#368">368</a>         } <em class="jxr_comment">//end while</em>
<a name="369" href="#369">369</a>     } <em class="jxr_comment">//end displayFreqData</em>
<a name="370" href="#370">370</a>       <em class="jxr_comment">//-----------------------------------------------------//</em>
<a name="371" href="#371">371</a> 
<a name="372" href="#372">372</a>     <em class="jxr_comment">//Recursive method to display a HufTree object.  The</em>
<a name="373" href="#373">373</a>     <em class="jxr_comment">// first call to this method should pass a value of 0</em>
<a name="374" href="#374">374</a>     <em class="jxr_comment">// for recurLevel.</em>
<a name="375" href="#375">375</a>     <strong class="jxr_keyword">void</strong> displayHuffTree(<a href="../../../../../../com/totsp/gwittir/client/util/compress/HuffTree.html">HuffTree</a> tree, <strong class="jxr_keyword">int</strong> recurLevel) {
<a name="376" href="#376">376</a>         recurLevel++;
<a name="377" href="#377">377</a> 
<a name="378" href="#378">378</a>         <strong class="jxr_keyword">if</strong> (tree instanceof HuffNode) {
<a name="379" href="#379">379</a>             <em class="jxr_comment">// This is a node, not a leaf.  Process it as a node.</em>
<a name="380" href="#380">380</a> 
<a name="381" href="#381">381</a>             <em class="jxr_comment">//Cast to type HuffNode.</em>
<a name="382" href="#382">382</a>             <a href="../../../../../../com/totsp/gwittir/client/util/compress/HuffNode.html">HuffNode</a> node = (HuffNode) tree;
<a name="383" href="#383">383</a> 
<a name="384" href="#384">384</a>             <em class="jxr_comment">// Get and save the left and right branches</em>
<a name="385" href="#385">385</a>             <a href="../../../../../../com/totsp/gwittir/client/util/compress/HuffTree.html">HuffTree</a> left = node.getLeft();
<a name="386" href="#386">386</a>             <a href="../../../../../../com/totsp/gwittir/client/util/compress/HuffTree.html">HuffTree</a> right = node.getRight();
<a name="387" href="#387">387</a> 
<a name="388" href="#388">388</a>             <em class="jxr_comment">//Display information that traces out the recursive</em>
<a name="389" href="#389">389</a>             <em class="jxr_comment">// traversal of the tree in order to display the</em>
<a name="390" href="#390">390</a>             <em class="jxr_comment">// contents of the leaves.</em>
<a name="391" href="#391">391</a>             System.out.print(<span class="jxr_string">"  Left to "</span> + recurLevel + <span class="jxr_string">" "</span>);
<a name="392" href="#392">392</a>             <em class="jxr_comment">//Make a recursive call.</em>
<a name="393" href="#393">393</a>             displayHuffTree(left, recurLevel);
<a name="394" href="#394">394</a> 
<a name="395" href="#395">395</a>             System.out.print(<span class="jxr_string">"  Right to "</span> + recurLevel + <span class="jxr_string">" "</span>);
<a name="396" href="#396">396</a>             <em class="jxr_comment">//Make a recursive call.</em>
<a name="397" href="#397">397</a>             displayHuffTree(right, recurLevel);
<a name="398" href="#398">398</a>         } <strong class="jxr_keyword">else</strong> {
<a name="399" href="#399">399</a>             <em class="jxr_comment">//This is a leaf.  Process it as such.</em>
<a name="400" href="#400">400</a>             <em class="jxr_comment">//Cast the object to type HuffLeaf.</em>
<a name="401" href="#401">401</a>             <a href="../../../../../../com/totsp/gwittir/client/util/compress/HuffLeaf.html">HuffLeaf</a> leaf = (HuffLeaf) tree;
<a name="402" href="#402">402</a>             System.out.println(<span class="jxr_string">"  Leaf:"</span> + (<strong class="jxr_keyword">char</strong>) leaf.getValue());
<a name="403" href="#403">403</a>         } <em class="jxr_comment">//end else</em>
<a name="404" href="#404">404</a> 
<a name="405" href="#405">405</a>         System.out.print(<span class="jxr_string">"  Back "</span>);
<a name="406" href="#406">406</a>     } <em class="jxr_comment">//end displayHuffTree</em>
<a name="407" href="#407">407</a> 
<a name="408" href="#408">408</a>     <em class="jxr_comment">//This method displays a message string as a series of</em>
<a name="409" href="#409">409</a>     <em class="jxr_comment">// characters each having a value of 1 or 0.</em>
<a name="410" href="#410">410</a>     <strong class="jxr_keyword">void</strong> displayRawDataAsBits() {
<a name="411" href="#411">411</a>         <strong class="jxr_keyword">for</strong> (<strong class="jxr_keyword">int</strong> cnt = 0, charCnt = 0; cnt &lt; rawData.length();
<a name="412" href="#412">412</a>                 cnt++, charCnt++) {
<a name="413" href="#413">413</a>             <strong class="jxr_keyword">char</strong> theCharacter = rawData.charAt(cnt);
<a name="414" href="#414">414</a>             String binaryString = Integer.toBinaryString(theCharacter);
<a name="415" href="#415">415</a> 
<a name="416" href="#416">416</a>             <em class="jxr_comment">//Append leading zeros as necessary to show eight</em>
<a name="417" href="#417">417</a>             <em class="jxr_comment">// bits per character.</em>
<a name="418" href="#418">418</a>             <strong class="jxr_keyword">while</strong> (binaryString.length() &lt; 8) {
<a name="419" href="#419">419</a>                 binaryString = <span class="jxr_string">"0"</span> + binaryString;
<a name="420" href="#420">420</a>             } <em class="jxr_comment">//end while loop</em>
<a name="421" href="#421">421</a> 
<a name="422" href="#422">422</a>             <strong class="jxr_keyword">if</strong> ((charCnt % 6) == 0) {
<a name="423" href="#423">423</a>                 <em class="jxr_comment">//Display 48 bits per line.</em>
<a name="424" href="#424">424</a>                 charCnt = 0;
<a name="425" href="#425">425</a>                 System.out.println(); <em class="jxr_comment">//new line</em>
<a name="426" href="#426">426</a>             } <em class="jxr_comment">//end if</em>
<a name="427" href="#427">427</a> 
<a name="428" href="#428">428</a>             System.out.print(binaryString);
<a name="429" href="#429">429</a>         } <em class="jxr_comment">//end for loop</em>
<a name="430" href="#430">430</a> 
<a name="431" href="#431">431</a>         System.out.println();
<a name="432" href="#432">432</a>     } <em class="jxr_comment">//end displayRawDataAsBits</em>
<a name="433" href="#433">433</a>       <em class="jxr_comment">//-----------------------------------------------------//</em>
<a name="434" href="#434">434</a> 
<a name="435" href="#435">435</a>     <em class="jxr_comment">//-----------------------------------------------------//</em>
<a name="436" href="#436">436</a> 
<a name="437" href="#437">437</a>     <em class="jxr_comment">//This method encodes an incoming String message using</em>
<a name="438" href="#438">438</a>     <em class="jxr_comment">// the Huffman encoding methodology.  The method also</em>
<a name="439" href="#439">439</a>     <em class="jxr_comment">// receives a reference to an empty data structure.</em>
<a name="440" href="#440">440</a>     <em class="jxr_comment">// This data structures is populated with encoding</em>
<a name="441" href="#441">441</a>     <em class="jxr_comment">// particulars required later by the decode method</em>
<a name="442" href="#442">442</a>     <em class="jxr_comment">// to decode and transform the encoded message back</em>
<a name="443" href="#443">443</a>     <em class="jxr_comment">// into the original String message.  Note that in</em>
<a name="444" href="#444">444</a>     <em class="jxr_comment">// order to keep this method simple, pad characters may</em>
<a name="445" href="#445">445</a>     <em class="jxr_comment">// be appended onto the end of the original</em>
<a name="446" href="#446">446</a>     <em class="jxr_comment">// message when it is encoded.  This is done to cause the</em>
<a name="447" href="#447">447</a>     <em class="jxr_comment">// number of bits in the encoded message to be a multiple</em>
<a name="448" href="#448">448</a>     <em class="jxr_comment">// of eight, thus causing the length of the encoded</em>
<a name="449" href="#449">449</a>     <em class="jxr_comment">// message to be an integral number of bytes.  Additional</em>
<a name="450" href="#450">450</a>     <em class="jxr_comment">// code would be required to avoid this at this point.</em>
<a name="451" href="#451">451</a>     <em class="jxr_comment">// However, it is easy to eliminate the extraneous</em>
<a name="452" href="#452">452</a>     <em class="jxr_comment">// characters during decoding if the length of the</em>
<a name="453" href="#453">453</a>     <em class="jxr_comment">// original message is known.</em>
<a name="454" href="#454">454</a>     <strong class="jxr_keyword">public</strong> byte[] encode(String rawData,
<a name="455" href="#455">455</a>         HashMap&lt;Character, String&gt; huffEncodeTable) {
<a name="456" href="#456">456</a>         <em class="jxr_comment">//Save the incoming parameters.</em>
<a name="457" href="#457">457</a>         <strong class="jxr_keyword">this</strong>.rawData = rawData;
<a name="458" href="#458">458</a>         <strong class="jxr_keyword">this</strong>.huffEncodeTable = huffEncodeTable;
<a name="459" href="#459">459</a> 
<a name="460" href="#460">460</a>         <em class="jxr_comment">//For illustration purposes only, enable the following</em>
<a name="461" href="#461">461</a>         <em class="jxr_comment">// two statements to display the original message as a</em>
<a name="462" href="#462">462</a>         <em class="jxr_comment">// stream of bits.  This can be visually compared with</em>
<a name="463" href="#463">463</a>         <em class="jxr_comment">// a similar display for the encoded  message later to</em>
<a name="464" href="#464">464</a>         <em class="jxr_comment">// illustrate the amount of compression provided by</em>
<a name="465" href="#465">465</a>         <em class="jxr_comment">// the encoding process.</em>
<a name="466" href="#466">466</a>         <em class="jxr_comment">/*</em>
<a name="467" href="#467">467</a> <em class="jxr_comment">            System.out.println("nRaw Data as Bits");</em>
<a name="468" href="#468">468</a> <em class="jxr_comment">            displayRawDataAsBits();</em>
<a name="469" href="#469">469</a> <em class="jxr_comment">        */</em>
<a name="470" href="#470">470</a> 
<a name="471" href="#471">471</a>         <em class="jxr_comment">//Create a frequency chart that identifies each of the</em>
<a name="472" href="#472">472</a>         <em class="jxr_comment">// individual characters in the original message and</em>
<a name="473" href="#473">473</a>         <em class="jxr_comment">// the number of times (frequency) that each character</em>
<a name="474" href="#474">474</a>         <em class="jxr_comment">// appeared in the message.</em>
<a name="475" href="#475">475</a>         createFreqData();
<a name="476" href="#476">476</a> 
<a name="477" href="#477">477</a>         <em class="jxr_comment">//For illustration purposes only, enable the following</em>
<a name="478" href="#478">478</a>         <em class="jxr_comment">// statement to display the contents of the frequency</em>
<a name="479" href="#479">479</a>         <em class="jxr_comment">// chart created above.</em>
<a name="480" href="#480">480</a>         <em class="jxr_comment">/*</em>
<a name="481" href="#481">481</a> <em class="jxr_comment">            displayFreqData();</em>
<a name="482" href="#482">482</a> <em class="jxr_comment">        */</em>
<a name="483" href="#483">483</a> 
<a name="484" href="#484">484</a>         <em class="jxr_comment">//Create a HuffLeaf object for each character</em>
<a name="485" href="#485">485</a>         <em class="jxr_comment">// identified in the frequency chart.  Store the</em>
<a name="486" href="#486">486</a>         <em class="jxr_comment">// HuffLeaf objects in a TreeSet object.  Each HuffLeaf</em>
<a name="487" href="#487">487</a>         <em class="jxr_comment">// object encapsulates the character as well as the</em>
<a name="488" href="#488">488</a>         <em class="jxr_comment">// number of times that the character appeared in the</em>
<a name="489" href="#489">489</a>         <em class="jxr_comment">// original message (the frequency).</em>
<a name="490" href="#490">490</a>         createLeaves();
<a name="491" href="#491">491</a> 
<a name="492" href="#492">492</a>         <em class="jxr_comment">//Assemble the HuffLeaf objects into  a Huffman tree</em>
<a name="493" href="#493">493</a>         <em class="jxr_comment">// (a HuffTree object). A Huffman tree is a special</em>
<a name="494" href="#494">494</a>         <em class="jxr_comment">// form of a binary tree  consisting of properly linked</em>
<a name="495" href="#495">495</a>         <em class="jxr_comment">// HuffNode objects and HuffLeaf objects.</em>
<a name="496" href="#496">496</a>         <em class="jxr_comment">//When the following method returns, the HuffTree</em>
<a name="497" href="#497">497</a>         <em class="jxr_comment">// object remains as the only object stored in the</em>
<a name="498" href="#498">498</a>         <em class="jxr_comment">// TreeSet object that previously contained all of the</em>
<a name="499" href="#499">499</a>         <em class="jxr_comment">// HuffLeaf objects.  This is because all of the</em>
<a name="500" href="#500">500</a>         <em class="jxr_comment">// HuffLeaf objects have been combined with HuffNode</em>
<a name="501" href="#501">501</a>         <em class="jxr_comment">// objects to form the tree.</em>
<a name="502" href="#502">502</a>         createHuffTree();
<a name="503" href="#503">503</a> 
<a name="504" href="#504">504</a>         <em class="jxr_comment">//Use the Huffman tree in a recursive manner to create</em>
<a name="505" href="#505">505</a>         <em class="jxr_comment">// a bit code for each character in the message.  The</em>
<a name="506" href="#506">506</a>         <em class="jxr_comment">// bit codes are different lengths with the shorter</em>
<a name="507" href="#507">507</a>         <em class="jxr_comment">// codes corresponding to the characters with a high</em>
<a name="508" href="#508">508</a>         <em class="jxr_comment">// frequency value and the longer codes corresponding</em>
<a name="509" href="#509">509</a>         <em class="jxr_comment">// to the characters with the lower frequency values.</em>
<a name="510" href="#510">510</a>         <em class="jxr_comment">//Note that the method call extracts the reference to</em>
<a name="511" href="#511">511</a>         <em class="jxr_comment">// the Huffman tree from the TreeSet object and passes</em>
<a name="512" href="#512">512</a>         <em class="jxr_comment">// that reference to the method.  This is necessary</em>
<a name="513" href="#513">513</a>         <em class="jxr_comment">// because the method is recursive and cannot</em>
<a name="514" href="#514">514</a>         <em class="jxr_comment">// conveniently work with the TreeSet object.</em>
<a name="515" href="#515">515</a>         <em class="jxr_comment">//This method populates the data structure that is</em>
<a name="516" href="#516">516</a>         <em class="jxr_comment">// required later to decode the encoded message.</em>
<a name="517" href="#517">517</a>         createBitCodes(theTree.first());
<a name="518" href="#518">518</a> 
<a name="519" href="#519">519</a>         <em class="jxr_comment">//For purposes of illustration only, enable the</em>
<a name="520" href="#520">520</a>         <em class="jxr_comment">// following two statements to display a table showing</em>
<a name="521" href="#521">521</a>         <em class="jxr_comment">// the relationship between the characters in the</em>
<a name="522" href="#522">522</a>         <em class="jxr_comment">// original message and the bitcodes that will replace</em>
<a name="523" href="#523">523</a>         <em class="jxr_comment">// those characters to produce the Huffman-encoded</em>
<a name="524" href="#524">524</a>         <em class="jxr_comment">// message.</em>
<a name="525" href="#525">525</a>         <em class="jxr_comment">/*</em>
<a name="526" href="#526">526</a> <em class="jxr_comment">            System.out.println();</em>
<a name="527" href="#527">527</a> <em class="jxr_comment">            displayBitCodes();</em>
<a name="528" href="#528">528</a> <em class="jxr_comment">        */</em>
<a name="529" href="#529">529</a> 
<a name="530" href="#530">530</a>         <em class="jxr_comment">//Encode the message into a String representation</em>
<a name="531" href="#531">531</a>         <em class="jxr_comment">// of the bits that will make up the final encoded</em>
<a name="532" href="#532">532</a>         <em class="jxr_comment">// message.  Also,the following method may optionally</em>
<a name="533" href="#533">533</a>         <em class="jxr_comment">// display the String showing the bit values that will</em>
<a name="534" href="#534">534</a>         <em class="jxr_comment">// appear in the final Huffman-encoded message.  This</em>
<a name="535" href="#535">535</a>         <em class="jxr_comment">// is useful for comparing back against the bits in</em>
<a name="536" href="#536">536</a>         <em class="jxr_comment">// the original message for purposes of evaluating the</em>
<a name="537" href="#537">537</a>         <em class="jxr_comment">// amount of compression provided by encoding the</em>
<a name="538" href="#538">538</a>         <em class="jxr_comment">// message.</em>
<a name="539" href="#539">539</a>         encodeToString();
<a name="540" href="#540">540</a> 
<a name="541" href="#541">541</a>         <em class="jxr_comment">//Populate a lookup table that relates eight bits</em>
<a name="542" href="#542">542</a>         <em class="jxr_comment">// represented as a String to every possible combinaion</em>
<a name="543" href="#543">543</a>         <em class="jxr_comment">// of eight actual bits.</em>
<a name="544" href="#544">544</a>         buildEncodingBitMap();
<a name="545" href="#545">545</a> 
<a name="546" href="#546">546</a>         <em class="jxr_comment">//Encode the String representation of the bits that</em>
<a name="547" href="#547">547</a>         <em class="jxr_comment">// make up the encoded message to the actual bits</em>
<a name="548" href="#548">548</a>         <em class="jxr_comment">// that make up the encoded message.</em>
<a name="549" href="#549">549</a>         <em class="jxr_comment">//Note that this method doesn't handle the end of the</em>
<a name="550" href="#550">550</a>         <em class="jxr_comment">// message very gracefully for those cases where the</em>
<a name="551" href="#551">551</a>         <em class="jxr_comment">// number of required bits is not a multiple of 8.  It</em>
<a name="552" href="#552">552</a>         <em class="jxr_comment">// simply adds enough "0" characters to the end to</em>
<a name="553" href="#553">553</a>         <em class="jxr_comment">// cause the length to be a multiple of 8.  This may</em>
<a name="554" href="#554">554</a>         <em class="jxr_comment">// result in extraneous characters at the end of the</em>
<a name="555" href="#555">555</a>         <em class="jxr_comment">// decoded message later.</em>
<a name="556" href="#556">556</a>         <em class="jxr_comment">//For illustration purposes only, this method may also</em>
<a name="557" href="#557">557</a>         <em class="jxr_comment">// display the extended version of the String</em>
<a name="558" href="#558">558</a>         <em class="jxr_comment">// representation of the bits for comparison with the</em>
<a name="559" href="#559">559</a>         <em class="jxr_comment">// non-extended version.</em>
<a name="560" href="#560">560</a>         encodeStringToBits();
<a name="561" href="#561">561</a> 
<a name="562" href="#562">562</a>         <em class="jxr_comment">//Return the encoded message.</em>
<a name="563" href="#563">563</a>         byte[] val = <strong class="jxr_keyword">new</strong> byte[binaryEncodedData.size()];
<a name="564" href="#564">564</a>         <strong class="jxr_keyword">for</strong>(<strong class="jxr_keyword">int</strong> i=0; i&lt;val.length; i++){
<a name="565" href="#565">565</a>             val[i] = binaryEncodedData.get(i);
<a name="566" href="#566">566</a>         }
<a name="567" href="#567">567</a>         <strong class="jxr_keyword">return</strong> val;
<a name="568" href="#568">568</a>     } <em class="jxr_comment">//end encode method</em>
<a name="569" href="#569">569</a>       <em class="jxr_comment">//-----------------------------------------------------//</em>
<a name="570" href="#570">570</a> 
<a name="571" href="#571">571</a>     <em class="jxr_comment">//The purpose of this method is to create actual bit data</em>
<a name="572" href="#572">572</a>     <em class="jxr_comment">// that matches the 1 and 0 characters in the</em>
<a name="573" href="#573">573</a>     <em class="jxr_comment">// stringEncodedData that represents bits with the 1 and</em>
<a name="574" href="#574">574</a>     <em class="jxr_comment">// 0 characters.</em>
<a name="575" href="#575">575</a>     <em class="jxr_comment">//Note that this method doesn't handle the end of the</em>
<a name="576" href="#576">576</a>     <em class="jxr_comment">// data very gracefully for those cases where the number</em>
<a name="577" href="#577">577</a>     <em class="jxr_comment">// of required bits is not a multiple of 8.  It simply</em>
<a name="578" href="#578">578</a>     <em class="jxr_comment">// adds enough "0" characters to the end to cause the</em>
<a name="579" href="#579">579</a>     <em class="jxr_comment">// length to be a multiple of 8.  This may result in</em>
<a name="580" href="#580">580</a>     <em class="jxr_comment">// extraneous characters at the end of the decoded</em>
<a name="581" href="#581">581</a>     <em class="jxr_comment">// message later. However, it isn't difficult to remove</em>
<a name="582" href="#582">582</a>     <em class="jxr_comment">// the extraneous characters at decode time as long as</em>
<a name="583" href="#583">583</a>     <em class="jxr_comment">// the length of the original message is known.</em>
<a name="584" href="#584">584</a>     <em class="jxr_comment">//For illustration purposes, this method may optionally</em>
<a name="585" href="#585">585</a>     <em class="jxr_comment">// display the extended version of the stringEncodedData</em>
<a name="586" href="#586">586</a>     <em class="jxr_comment">// for comparison with the non-extended version.</em>
<a name="587" href="#587">587</a>     <em class="jxr_comment">//Note that the binary Huffman-encoded data produced by</em>
<a name="588" href="#588">588</a>     <em class="jxr_comment">// this method is stored in a data structure of type</em>
<a name="589" href="#589">589</a>     <em class="jxr_comment">// ArrayList &lt;Byte&gt;.</em>
<a name="590" href="#590">590</a>     <strong class="jxr_keyword">void</strong> encodeStringToBits() {
<a name="591" href="#591">591</a>         <em class="jxr_comment">//Extend the length of the stringEncodedData to cause</em>
<a name="592" href="#592">592</a>         <em class="jxr_comment">// it to be a multiple of 8.</em>
<a name="593" href="#593">593</a>         <strong class="jxr_keyword">int</strong> remainder = stringEncodedData.length() % 8;
<a name="594" href="#594">594</a> 
<a name="595" href="#595">595</a>         <strong class="jxr_keyword">for</strong> (<strong class="jxr_keyword">int</strong> cnt = 0; cnt &lt; (8 - remainder); cnt++) {
<a name="596" href="#596">596</a>             stringEncodedData += <span class="jxr_string">"0"</span>;
<a name="597" href="#597">597</a>         } <em class="jxr_comment">//end for loop</em>
<a name="598" href="#598">598</a> 
<a name="599" href="#599">599</a>         <em class="jxr_comment">//For illustration purposes only, enable the following</em>
<a name="600" href="#600">600</a>         <em class="jxr_comment">// two statements to display the extended</em>
<a name="601" href="#601">601</a>         <em class="jxr_comment">// stringEncodedData in the same format as the</em>
<a name="602" href="#602">602</a>         <em class="jxr_comment">// original stringEncodedData.</em>
<a name="603" href="#603">603</a> 
<a name="604" href="#604">604</a>         <em class="jxr_comment">//Extract the String representations of the required</em>
<a name="605" href="#605">605</a>         <em class="jxr_comment">// eight bits.  Generate eight actual matching bits by</em>
<a name="606" href="#606">606</a>         <em class="jxr_comment">// looking the bit combination up in a table.</em>
<a name="607" href="#607">607</a>         <strong class="jxr_keyword">for</strong> (<strong class="jxr_keyword">int</strong> cnt = 0; cnt &lt; stringEncodedData.length(); cnt += 8) {
<a name="608" href="#608">608</a>             String strBits = stringEncodedData.substring(cnt, cnt + 8);
<a name="609" href="#609">609</a>             byte realBits = encodingBitMap.get(strBits);
<a name="610" href="#610">610</a>             binaryEncodedData.add(realBits);
<a name="611" href="#611">611</a>         }
<a name="612" href="#612">612</a>     }
<a name="613" href="#613">613</a> 
<a name="614" href="#614">614</a>     <em class="jxr_comment">//This method encodes the message into a String</em>
<a name="615" href="#615">615</a>     <em class="jxr_comment">// representation of the bits that will make up the final</em>
<a name="616" href="#616">616</a>     <em class="jxr_comment">// encoded message.  The String consists of only 1 and 0</em>
<a name="617" href="#617">617</a>     <em class="jxr_comment">// characters where each character represents the state</em>
<a name="618" href="#618">618</a>     <em class="jxr_comment">// of one of the bits in the Huffman-encoded message.</em>
<a name="619" href="#619">619</a>     <em class="jxr_comment">//Also for illustration purposes, this method optionally</em>
<a name="620" href="#620">620</a>     <em class="jxr_comment">// displays the String showing the bit values that will</em>
<a name="621" href="#621">621</a>     <em class="jxr_comment">// appear in the Huffman-encoded message.</em>
<a name="622" href="#622">622</a>     <strong class="jxr_keyword">void</strong> encodeToString() {
<a name="623" href="#623">623</a>         StringBuffer tempEncoding = <strong class="jxr_keyword">new</strong> StringBuffer();
<a name="624" href="#624">624</a> 
<a name="625" href="#625">625</a>         <strong class="jxr_keyword">for</strong> (<strong class="jxr_keyword">int</strong> cnt = 0; cnt &lt; rawData.length(); cnt++) {
<a name="626" href="#626">626</a>             tempEncoding.append(huffEncodeTable.get(rawData.charAt(cnt)));
<a name="627" href="#627">627</a>         }
<a name="628" href="#628">628</a> 
<a name="629" href="#629">629</a>         stringEncodedData = tempEncoding.toString();
<a name="630" href="#630">630</a> 
<a name="631" href="#631">631</a>         <em class="jxr_comment">//For illustration purposes, enable the following two</em>
<a name="632" href="#632">632</a>         <em class="jxr_comment">// statements to display the String showing the bit</em>
<a name="633" href="#633">633</a>         <em class="jxr_comment">// values that will appear in the Huffman-encoded</em>
<a name="634" href="#634">634</a>         <em class="jxr_comment">// message.  Display 48 bits to the line except for</em>
<a name="635" href="#635">635</a>         <em class="jxr_comment">// the last line, which may be shorter, and which may</em>
<a name="636" href="#636">636</a>         <em class="jxr_comment">// not be a multiple of 8 bits.</em>
<a name="637" href="#637">637</a>         <em class="jxr_comment">/*</em>
<a name="638" href="#638">638</a> <em class="jxr_comment">            System.out.println("nString Encoded Data");</em>
<a name="639" href="#639">639</a> <em class="jxr_comment">            display48(stringEncodedData);</em>
<a name="640" href="#640">640</a> <em class="jxr_comment">        */</em>
<a name="641" href="#641">641</a>     } <em class="jxr_comment">//end encodeToString</em>
<a name="642" href="#642">642</a>       <em class="jxr_comment">//-----------------------------------------------------//</em>
<a name="643" href="#643">643</a> }
</pre>
<hr/><div id="footer">This page was automatically generated by <a href="http://maven.apache.org/">Maven</a></div></body>
</html>

